Turbo codes have received considerable attention since their introduction in 1993. This is due to their powerful error correcting capability, reasonable complexity, and flexibility in terms of accommodating different block lengths and code rates.
FIG. 1 illustrates one common turbo-code encoder that uses two recursive systematic convolutional (RSC) encoders 100 and 104 operating in parallel, with the RSC encoder 104 preceded by an interleaver 102, and a puncturing unit 106. The same data bits di=d(i), i.e. information bits plus possible overhead bits such as error detection and trellis termination bits, with the index i indicating bit location in a data bit sequence, are fed into two RSC encoders 100, 104, but the interleaver 102 permutes, i.e. re-orders the data bits according to a pre-determined interleaving rule before passing the data symbols/bits to the RSC encoder 104. Encoders 100 and 104 generate parity symbols p1(i) and p,2(i) which are provided to the puncturing unit 106. The puncturing unit 106 punctures the parity symbols generated by the RSC encoders and, optionally, some of the source data symbols. The source symbols di and corresponding punctured parity symbols p1(i) and p,2(i) generated by the encoders 100 and 104 form encoded code words which are provided to a modulator, which is not shown. The turbo code codewords consist of one set of data bits and the two sets of parity bits generated by the two RSC encoders 100, 104. Assuming rate 1/2 constituent codes, the nominal overall code rate, without any puncturing, is 1/3. The puncturing unit 106 is used to achieve higher code rates by removing some of the data and/or parity symbols from the codewords.
The decoding process is typically performed in an iterative manner by exchanging soft information, often called extrinsic information, between two constituent RSC decoders corresponding to the RSC encoders 100 and 104, with one of the two constituent decoders preceded by the interleaver to decode the interleaved code generated by the RSC decoder 104. Each constituent decoder uses a soft-in/soft-out (SISO) algorithm such as the Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm well known in the art. Versions of this algorithm are also referred to as the maximum a posteriori probability (MAP) algorithm or more precisely, in the context of soft iterative decoding, as the a posteriori probability (APP) algorithm. These algorithms and their log-domain variations, often referred to as the log-MAP, log-APP, max-log-MAP and max-log-APP algorithms, are discussed, for example, in a paper by P. Robertson, E. Villebrun, and P. Hoeher, entitled “A Comparison of Optimal and Suboptimal MAP Decoding Algorithms Operating in the Log Domain”, Proceedings of the IEEE International Conference on Communications, June 1995, pp. 1009-1013.
Turbo code error rate performance is typically characterized by two important regions, namely the waterfall region and the error flare region in an error-rate vs. signal-to-noise ratio (SNR) curve. The waterfall region is associated with low to moderate SNR values. In this region, the slope of the error-rate curve drops rapidly as the SNR increases. The error flare region is associated with moderate to high SNR values. In this region, the error-rate curve suffers from flattening or flaring, making it difficult to further improve the error rate performance without a significant increase in the SNR.
Interleaving is a practice well known in the art. It is a method of arranging or permuting elements within a block. In a turbo-code encoder the elements are typically data bits or data symbols. In a turbo-code decoder the data elements are typically soft data samples from the receiver.
Interleaving is a key component of turbo codes, and interleaver strategy plays a critical role in determining code performance. This is true for both Turbo Code classes, i.e., Parallel Concatenated Convolutional Code (PCCC) disclosed in U.S. Pat. No. 5,446,747 and illustrated in FIG. 1, as well as for Serially Concatenated Convolutional Code (SCCC). In both cases block interleavers are typically used, as the data stream is divided into blocks of finite size before performing the encoding and decoding operations.
Interleavers can be defined and implemented in a number of different ways. FIG. 2 illustrates a definition used herein. The interleaver reads from a vector 108 of input symbols or samples, din, and writes to a vector 111 of interleaved or permuted output samples, dout. The input samples 108 are read using read indexes i=0 . . . K−1, where K is the interleaver length. The interleaver vector I defines the order in which the samples from the input vector 108 form the output vector 111. That is, the i-th input, read from location i in the input vector 108 is written to location I(i) in the output vector 111. The interleaver is completely defined by the write vector I. The elements being interleaved can be symbols used in an encoder, such as standard bits, or they can be signal samples or soft reliability values corresponding to transmitted symbols in a decoder. To be general, the symbols or samples will simply be referred to as elements. It is understood that interleavers are required in both encoders and decoders and that the term interleaver is also used to refer to a de-interleaver.
FIG. 3 illustrates components of a conventional interleaver 102 in the context of the turbo encoder. The input of the interleaver is stored in a memory 110, which is at least as large as the interleaver block size, i.e. K symbols. An indexing engine 112 re-orders the symbols stored in the memory 110 according to the order provided by the indices 114. The re-ordered symbols are stored in memory 116 and provided as output. In some cases the interleaver can provide the re-ordered symbols directly without the need for having both memory 110 and 116.
Two common interleaver types are the “random” interleaver and the so-called “S-random” or “spread” interleaver. The term “interleaver spread” refers to a spacing between symbols before and after interleaving in the data sequence. It is known in the art that good spreading properties of an interleaver are desirable for both fast convergence during iterative decoding and good distance properties between codewords generated by the encoder. A high codeword, e.g. Hamming, distance is desirable for both lowering the error flare and for making the flare region of the BER vs. SNR curve as steep as possible. Hamming distance is the minimum number of symbols that must be changed in a code word for a first codeword to become a second codeword. The further apart two codewords are, the more a signal can be corrupted while retaining the ability for the decoder to properly decode the message. It is also important to reduce the number of codewords at or near the minimum distance.
Examples of known high-spread interleavers include dithered golden interleavers, and low extrinsic correlation interleavers. A high-spread random (HSR) interleaver which provides excellent performance results is disclosed in a paper entitled “New High-Spread High-Distance Interleavers for Turbo-codes” presented at 20th Biennial Symposium on Communications, Kingston Ontario, Canada, pp. 3-7, May 28-31, 2000 by S. Crozier, an inventor of the current invention, and in Canadian Patent Application No. 2,348,941 issued to S. Crozier, which are incorporated herein by reference. Efficient high-spread interleavers with reduced memory requirements are dithered relative prime (DRP) interleavers, which are disclosed in U.S. Pat. No. 6,857,087 issued to S. Crozier and assigned to the assignee of the instant application, which is incorporated herein by reference. The HSR and DRP approaches use a definition of spread which differs from that typically used to design S-random interleavers, and is more closely related to the distance properties of Turbo-codes; see e.g. U.S. Pat. No. 6,857,087 for more details.
The term ‘data puncturing’ as used herein means that in the output of the turbo encoder some of the data symbols have been punctured, i.e. dropped, instead of puncturing just the parity symbols. This means that the turbo code is no longer a systematic code, but is only partially systematic. The most common puncturing method is to only puncture the parity symbols, but promising performance has also been obtained with limited puncturing of the data symbols.
Data puncturing that provides an overall punctured code rate of 1/2 has been investigated in a paper by I. Land and P. Hoeher, entitled “Partially Systematic Rate 1/2 Turbo Codes”, presented at 2nd International Symposium on Turbo Codes, Brest, France, pp. 287-290, Sep. 4-7, 2000, which is incorporated herein by reference. The results disclosed by Land and Hoeher showed, however, only a modest improvement in performance with data puncturing. This was partly due to the fact that only random interleavers were investigated, with no other constraints placed on the interleavers to optimize the overall code performance. Results for 8 and 16-state RSC encoders for higher code rates with data puncturing are disclosed in U.S. Pat. No. 6,857,087 to S. Crozier and P. Guinand, and a paper by S. Crozier and P. Guinand, “Distance Upper Bounds and True Minimum Distance Results for Turbo-Codes Designed with DRP Interleavers”, 3rd International Symposium on Turbo Codes, Brest, France, pp. 169-172, Sep. 1-5, 2003, where it is shown that by improving the interleaver design, a more significant improvement can be achieved in error flare performance for encoders with data puncturing.
The code rate of a turbo code with puncturing is given byR=1/(R0+R1+R2)  (1)
where R0=N0/D0 is the data throughput rate, R1=N1/D1 is the first parity (par1) throughput rate, R2=N2/D2 is the second parity (par2) throughput rate.
Typically, puncturing is performed using relatively short repeating puncture masks for each of the data and parity streams. Each mask contains a sequence of 0's and 1's where, by convention, a ‘1’ indicates a selected, or kept, bit and a ‘0’ indicates a punctured, or removed, bit. The denominators, D0, D1 and D2, represent the lengths of the puncture masks and the numerators, N0, N1 and N2, are the number of ‘1’s in the masks. Without any puncturing R0=R1=R2=1 and R=1/3. If by way of example a code rate of R=2/3 is desired, without any data puncturing it might be obtained using repeating puncture masks of (Pdata, Ppar1, Ppar2)=(1, 0100, 0010), where Pdata is the puncturing mask used for puncturing the data symbols, and Ppar1, Ppar2 are the puncture masks used for puncturing the first and second parity symbols generated by the encoders 100, 104 respectively. In this example, N0=1, D0=1, N1=1, D1=4, N2=1 and D2=4, which corresponds to puncturing, i.e. dropping 3 out of each 4 parity bits, which may be detrimental to error correction performance of the punctured code. This problem can be addressed by a small amount of data puncturing. Considering 1-in-4 data puncturing as an example, the code rate R=2/3 might be obtained using the repeating puncture masks of (Pdata, Ppar1, Ppar2)=(0111, 10010010, 01001001), so that additional parity bit/symbols can be kept for potentially improved performance.
A small amount of data puncturing, in exchange for keeping more parity bits, can significantly improve the distance property of the resulting code and thus the flare performance. Intuitively, this is because most of the codeword distance, especially for the low input-weight codewords, tends to come from the parity bits. Therefore the better the interleaver design, i.e., the larger proportion of distance that comes from the parity symbols, the better data puncturing should work to improve the distance. It has also been found that the convergence, i.e. the waterfall region performance can also be improved with small amounts of data puncturing. However, puncturing too many data symbols can significantly degrade the convergence performance. Further, too much data puncturing can also cause catastrophic effects and worsen distance properties of the punctured codeword and thus degrade error flare performance.
One problem with puncturing of data symbols in prior art turbo codes with conventional interleaver designs is an effective “scrambling” of the puncturing mask associated with the second code by the interleaver. That is, the interleaver 102 in effect permutes the repeated data puncture mask used for the first code, which may result in sub-optimal data puncturing for the second code. Moreover, since most high-performance turbo code interleavers utilize random or pseudo-random permutation rules, the data puncturing associated with the second encoder 104 usually has a random nature. With the effectively random data puncturing, the distance properties and soft decoding properties associated with the second constituent decoder which decodes interleaved data are difficult to predict, control, and/or optimize, and catastrophic or near catastrophic puncturing might occur if several punctured data symbols get interleaved close together.
Recently, I. A. Chatzigeorgiou, M. R. D. Rodrigues, I. J. Wassell and R. Carrasco in a paper entitled “Punctured Binary Turbo-Codes with Optimized Performance”, published in Proceedings of the 62nd IEEE Vehicular Technology Conference (VTC Fall 2005), Dallas, USA, Sep. 25-28, 2005, tried to address this problem by disclosing an l-bit periodic random interleaver that imposes a puncture mask related constraint on symbol positions in the interleaved sequence; namely, if l is the length of the data puncturing pattern Pd, the l-bit periodic random interleaver of Chatzigeorgiou et al maps the data puncturing pattern Pd into the same pattern Pd, by permuting i-th symbol of the input sequence of data symbols to one of a symbol locations (i+nl) in the interleaved sequence, where n is a random integer number.
The encoding method disclosed by Chatzigeorgiou et al, although solving the problem of interleaver-induced catastrophic or near-catastrophic puncturing, has however significant drawbacks and undesirable limitations. First, the encoder of Chatzigeorgiou et al utilizes homogeneous puncturing patterns, wherein the puncturing bits are uniformly distributed among the systematic, i.e. data, and the parity streams of the turbo encoder. This limits the highest achievable code rate to 2/3, which is an undesirable limitation disadvantageously affecting the codes' information efficiency. Second, the encoding method of Chatzigeorgiou et al imposes unnecessarily strict limitations on the interleaver design, thereby severely limiting the choice of interleavers, and making it difficult to find an interleaver providing good spread and distance properties, and fast convergence of the decoding process.
Accordingly, an object of this invention is to provide a method of encoding utilizing data puncturing and an improved puncture-constrained interleaving for providing enhanced error correction and decoding convergence performance, and an encoder utilizing said method.